// 题目要求：
// 给一个大小为 n 的顺序表，里面存的是金币数量
// 假设以 i 位置讨论，取 i 位置的金币能获得 left * coins[i] * right 的积分数
// left 是左边金币的数量，right 是右边金币的数量
// 如果左右没有金币，则视为 1
// 计算最多能获得多少积分

// 解题思路：
// 动态规划，定义 dp[i][j] 表示从 [i, j] 区间能获得的最大积分，假设最后拿走的金币的位置是 k，i <= k <= j
// dp[i][j] = max(dp[i][k - 1] + dp[k + 1][j] + coins[i - 1] * coins[k] * coins[j + 1])
// 如果 k - 1 < i 或者 k + 1 > j，没有关系，因为 dp 表初始化为 0，不影响最终结果
// 填表顺序：因为 (i, k - 1) 在 (i, j) 的左边，(k + 1, j) 在 (i, j) 的下面，因此填表顺序是从下往上每一行，每一行从左往右

import java.util.*;


public class Coins {
    public int getCoins (ArrayList<Integer> coins) {
        int n = coins.size();
        int[] t = new int[n + 2];

        t[0] = 1; t[n + 1] = 1;
        for(int i = 0; i < n; i++) t[i + 1] = coins.get(i);

        int[][] dp = new int[n + 2][n + 2];
        for(int i = n; i >= 1; i--){
            for(int j = 1; j <= n; j++){
                for(int k = i; k <= j; k++){
                    dp[i][j] = Math.max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + t[i - 1] * t[k] * t[j + 1]);
                }
            }
        }

        return dp[1][n];
    }
}
